Міністерство освіти і науки
Національний університет “Львівська політехніка”
Кафедра ЕОМ
/
Звіт
з лабораторної роботи № 3
з дисципліни: “Алгоритми та методи обчислень”
на тему: “ Розробка та дослідження ефективності методів сортування ”
Мета лабораторної роботи
Вивчення, реалізація та дослідження ефективності методів сортування даних.
Теоретичні відомості
Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування.
Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв'язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все часова ефективність та економне використання пам'яті. Згідно цих вимог, прості алгоритми сортування (такі, як сортування вибором і сортування вставкою) не є дуже ефективними.
Алгоритм сортування обміном, хоча і завершує свою роботу (оскільки він використовує лише цикли з параметром і в тілі циклів параметри примусово не змінюються) і не використовує допоміжної пам'яті, але займає багато часу. Навіть, якщо внутрішній цикл не містить жодної перестановки, то дії будуть повторюватись до тих пір, поки не завершиться зовнішній цикл.
Алгоритм сортування вибором ефективніше сортування обміном за критерієм М(n), тобто за кількістю перестановок, але також є не дуже ефективним. З цих причин було розроблено деякі нові алгоритми сортування, що отримали назву швидких алгоритмів сортування. Це такі алгоритми, як сортування деревом, пірамідальне сортування, швидке сортування Хоара та метод цифрового сортування.
Метою роботи є ознайомлення з алгоритмами сортування, спроба проаналізувати їх і написати програму, яка б виконувала сортування деякої послідовності за допомогою різних алгоритмів сортування.
Необхідність відсортувати які-небудь величини виникає в програмуванні дуже часто. Існують ситуації, коли попереднє сортування даних дозволяє скоротити змістовну частину алгоритму в декілька разів, а час його роботи - у десятки разів.
Однак справедливе й зворотне. Яким би гарним і ефективним не був обраний алгоритм, але якщо в якості підзадачі він використовує "поганє" сортування, то вся робота з його оптимізації виявляється марною. Невдало реалізоване сортування вхідних даних здатне помітно знизити ефективність алгоритму в цілому.
Завдання Рекурсивне сортування злиттям
Лістинг програми:
#include <iostream>
using namespace std;
void Merge(int *A, int first, int last) //функція, яка зливає масиви
{
int middle, start, final, j;
int *mas = new int[100];
middle = (first + last) / 2; // обрахування середнього елемента
start = first; //початок лівої частини
final = middle + 1; //початок правої частини
for (j = first; j <= last; j++) //виконання від початку до кінця
if ((start <= middle) && ((final>last) || (A[start]<A[final])))
{
mas[j] = A[start];
start++;
}
else
{
mas[j] = A[final];
final++;
}
//повернення результату в список
for (j = first; j <= last; j++) A[j] = mas[j];
delete[]mas;
};
//рекурсивна процедура сортування
void MergeSort(int *A, int first, int last)
{
{
if (first<last)
{
MergeSort(A, first, (first + last) / 2); //сортування лівої частини
MergeSort(A, (first + last) / 2 + 1, last); //сортування правої частини
Merge(A, first, last); //злиття двох частин
}
}
};
//головна функція
void main()
{
setlocale(LC_ALL, "Rus");
int i, n;
int *A = new int[100];
cout << "Розмiр масиву: > "; cin >> n;
for (i = 1; i <= n; i++)
{
cout << i << " елемент > "; cin >> A[i];
}
MergeSort(A, 1, n); //виклик сортувальної процедури
cout << "Впорядкований масив: "; //вивід впорядкованого масиву
for (i = 1; i <= n; i++) cout << A[i] << " ";
delete[]A;
system("pause>>void"); // >> заміняє stdout програми на імя файлу,вказане після знаку і весь вивід виконується у ...
